﻿using System;
using System.Collections.Generic;
using System.Text;

namespace 算法
{
    public class _97jcStr
    {
        public bool IsInterleave(string s1, string s2, string s3)
        {
            if (s1.Length + s2.Length != s3.Length) return false;//长度不一样肯定是错的
            int n1 = s1.Length, n2 = s2.Length;
            bool[,] dp = new bool[n1 + 1, n2 + 1];
            dp[0, 0] = true;
            for (int i = 1; i <= n1; ++i)
            {
                dp[i, 0] = dp[i - 1, 0] && (s1[i - 1] == s3[i - 1]);
            }
            for (int i = 1; i <= n2; ++i)
            {
                dp[0, i] = dp[0, i - 1] && (s2[i - 1] == s3[i - 1]);
            }
            for (int i = 1; i <= n1; i++)
            {
                for (int j = 1; j <= n2; j++)
                {
                    dp[i, j] = dp[i - 1, j] && s1[i - 1] == s3[i - 1 + j] || dp[i, j - 1] && s2[j - 1] == s3[i - 1 + j];
                }
            }
            return dp[n1, n2];
        }
    }
}
